package code.classic150on2025;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author 26029
 * @date 2025/6/22
 * @description
 */
public class Matrix {
    // 36. 有效的数独
    public boolean isValidSudoku(char[][] board) {
        boolean[] map = null;
        // 行
        for (int i = 0; i < 9; i++) {
            map = new boolean[10];
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.')
                    continue;
                if (map[board[i][j] - '0'])
                    return false;
                map[board[i][j] - '0'] = true;
            }
        }
        // 列
        for (int j = 0; j < 9; j++) {
            map = new boolean[10];
            for (int i = 0; i < 9; i++) {
                if (board[i][j] == '.')
                    continue;
                if (map[board[i][j] - '0'])
                    return false;
                map[board[i][j] - '0'] = true;
            }
        }
        // 块
        boolean[][] maps = new boolean[10][10];
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.')
                    continue;
                int blockNum = getBlockNum(i, j);
                if (maps[blockNum][board[i][j] - '0'])
                    return false;
                maps[blockNum][board[i][j] - '0'] = true;
            }
        }
        return true;
    }

    private int getBlockNum(int i, int j) {
        return (i / 3) * 3 + (j / 3);
    }

    // 54. 螺旋矩阵
    public List<Integer> spiralOrder(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] dir  = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int nowDir = 0;
        int count = 0;
        int num = m * n;
        int x = 0, y = 0;
        List<Integer> ans = new ArrayList<>();
        while (count < num) {
            ans.add(matrix[x][y]);
            count++;
            matrix[x][y] = Integer.MAX_VALUE;
            int nextX = x + dir[nowDir][0], nextY = y + dir[nowDir][1];
            if (nextX < 0 || nextX >= m || nextY < 0 || nextY >= n || matrix[nextX][nextY] == Integer.MAX_VALUE) {
                nowDir = (nowDir + 1) % 4;
            }
            x += dir[nowDir][0];
            y += dir[nowDir][1];
        }
        return ans;
    }

    // 48. 旋转图像
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        int times = n / 2;
        for (int i = 0; i < times; i++) {
            // 左上(i,i) 右上(i,n-1-i) 左下(n-1-i,i) 右下(n-1-i,n-1-i)
            // 一行(一列)有n-i*2个，需要处理n-i*2-1个
            for (int j = 0; j < n - i * 2 - 1; j++) {
                int[] upLeftPos = new int[]{i, i + j};
                int[] upRightPos = new int[]{i + j, n - 1 - i};
                int[] downRightPos = new int[]{n - 1 - i, n - 1 - i - j};
                int[] downLeftPos = new int[]{n - 1 - i - j, i};
                int temp = matrix[upLeftPos[0]][upLeftPos[1]];
                matrix[upLeftPos[0]][upLeftPos[1]] = matrix[downLeftPos[0]][downLeftPos[1]];
                matrix[downLeftPos[0]][downLeftPos[1]] = matrix[downRightPos[0]][downRightPos[1]];
                matrix[downRightPos[0]][downRightPos[1]] = matrix[upRightPos[0]][upRightPos[1]];
                matrix[upRightPos[0]][upRightPos[1]] = temp;
            }
        }
    }

    // 73. 矩阵置零
    public void setZeroes(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        boolean is0line = false;
        boolean is0row = false;
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) {
                is0line = true;
                break;
            }
        }
        for (int j = 0; j < n; j++) {
            if (matrix[0][j] == 0) {
                is0row = true;
                break;
            }
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                int now = matrix[i][j];
                if (now == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
        for (int i = 1; i < m; i++) {
            if (matrix[i][0] == 0) {
                for (int j = 0; j < n; j++) {
                    matrix[i][j] = 0;
                }
            }
        }
        for (int j = 1; j < n; j++) {
            if (matrix[0][j] == 0) {
                for (int i = 0; i < m; i++) {
                    matrix[i][j] = 0;
                }
            }
        }
        if (is0line) {
            for (int i = 0; i < m; i++) {
                matrix[i][0] = 0;
            }
        }
        if (is0row) {
            for (int j = 0; j < n; j++) {
                matrix[0][j] = 0;
            }
        }
    }

    // 289. 生命游戏
    public void gameOfLife(int[][] board) {
        int m = board.length;
        int n = board[0].length;
        int[][] dirs = new int[][]{{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
        // 0代表当前死下一步死——2代表当前死下一步活
        // 1代表当前活下一步活——3代表当前活下一步死
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int aliveCells = 0;
                for (int k = 0; k < dirs.length; k++) {
                    int cellX = i + dirs[k][0];
                    int cellY = j + dirs[k][1];
                    if (cellX < 0 || cellX >= m || cellY < 0 || cellY >= n)
                        continue;
                    if (board[cellX][cellY] == 1 || board[cellX][cellY] == 3)
                        aliveCells++;
                }
                if (board[i][j] == 1) {
                    if (aliveCells < 2 || aliveCells > 3)
                        board[i][j] = 3;
                } else if (board[i][j] == 0) {
                    if (aliveCells == 3)
                        board[i][j] = 2;
                }
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 2)
                    board[i][j] = 1;
                else if (board[i][j] == 3)
                    board[i][j] = 0;
            }
        }
    }

    public static void main(String[] args) {
        Matrix m = new Matrix();
        m.setZeroes(new int[][]{{1,2,3,4},{5,0,7,8},{0,10,11,12},{13,14,15,0}});
    }
}
